package q149_maxPoints;

import java.util.HashMap;
import java.util.Map;

public class Solution_2 {
    /*
    相较于方法1 这里只是进行了有些剪枝操作
     */
    public int maxPoints(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int ret = 0;
        // 依次遍历每一个点作为'基准点', 统计后续所有点与基准点的斜率
        for (int i = 0; i < n; i++) {
            if (ret >= n - i || ret > n / 2) {
                // 如果当前答案（共线点的数量）已经大于等于剩余点的数量, 或是已经大于总点数的一半, 表明后续已经不会再有超过这个值的可能，可以直接返回
                break;
            }
            // 这个HashMap是用来表示'本斜率 -> 本斜率能够穿过的点数量'的映射
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                // 当前'基准点': points[i]
                // 当前'其它点': points[j]
                // 斜率k = deltaY / deltaX = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0])
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                // 这里我们需要讨论一些细节和特殊情况
                // 因为涉及除法, 所以有可能出现浮点精度不够，分子分母可能出现0，假分数，分子分母符号不同的问题
                // 1. 浮点精度不够: 我们可以不进行除法运算，直接记录分子'deltaY'和分母'deltaX'的值
                // 2. 分子分母可能出现0的问题: 分子为0表示斜率为0, 平行于x轴, 分母为0, 斜率无穷大, 垂直与x轴(不会同时为0，因为不共点)
                // 3. 假分数问题: '1/2' 与 '2/4'是一样的
                // 4. 分子分母符号不同: '-1/2' 与 '1/-2'是一样的
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(Math.abs(x), Math.abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                // 因为题目中的数据范围是[-10000, 10000], 经过这些变换后
                // deltaX: [0, 20000]
                // deltaY: [-20000, 20000]
                // 我们就可以用一个trick, 把这两个值映射成一个i32范围内的整数: deltaX + 20001 * deltaY 大概[-400000000, 400000000]
                int key = y + x * 20001;

                // 计算好key后我们就可以把这个值加入hashmap中
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            int maxn = 0;
            // 本轮的最后，让我们统计最多的k值，注意这里是斜率的数量，我们需要点的数量，所以最后还需要+1(一个斜率代表2个点，2个相同的斜率表示3个点...)
            for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
                int num = entry.getValue();
                maxn = Math.max(maxn, num + 1);
            }
            ret = Math.max(ret, maxn);
        }
        return ret;
    }

    // 比较清晰的 不过少了一些剪枝
    public int maxPointsBetter(int[][] ps) {
        int n = ps.length;
        int ans = 1;
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            // 由当前点 i 发出的直线所经过的最多点数量
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = ps[i][0], y1 = ps[i][1], x2 = ps[j][0], y2 = ps[j][1];
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                // 直接用字符串存下来 避免了很多问题
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }


    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }

}
